The present invention relates to a method for converting OFF (object file format) from three-dimensional polygon data into quad edge data structure.
Generally, typical shapes of data in computer graphics are three-dimensional polygons or triangles.
Three-dimensional polygons and triangles are displayed on a computer screen through a rendering process, which requires an efficient algorithm.
Three-dimensional polygon data are generated, modified, or added in application areas such as rendering, virtual reality, and animation.
To perform such operations efficiently, various data structures have been proposed, and quad edge data structure is one of them.
Quad edge data structure is an edge-based data structure and is able to describe graph and dual graph at the same time. In addition, quad edge data structure employs a splice operator, which is a topological operator.
Even though quad edge is a sufficient data structure for its purposes, an efficient method converting conventional data structure into quad edge data structure has not been discovered.
A method for converting OFF (object file format) of three-dimensional polygon data into a quad edge data structure is provided.
The method in accordance with an embodiment of the present invention includes the following steps. A first step is to determine if an input triangle in object file format is a whole new triangle. An additional step is to find two edges and perform a splice operation if the input triangle is a whole new triangle in the determination step. The two edges are connected with a vertex. A step is to find a quad edge from a vertex link of the quad edge data structure if the input triangle is not a whole new triangle in the determination step. The vertex link has a counterclockwise sequence. A further step is to find a candidate edge for a splice operation by comparing the link generated in the preprocessing stage and the vertex link of the quad edge data structure and performing the splice operation on the candidate edge and a new quad edge.
The method implemented in a computer system in accordance with an embodiment of the present invention includes the following steps. A first step is to determine if an input triangle of object file format is a whole new triangle. An additional step is to find two edges and perform a splice operation if the input triangle is a whole new triangle in the determination step. The two edges are connected with a vertex. A further step is to find a quad edge from a vertex link of the quad edge data structure if the input triangle is not a whole new triangle in the determination step. The vertex link has a counterclockwise sequence. Another additional step is to find a candidate edge for a splice operation by comparing the link generated in the preprocessing stage and the vertex link of the quad edge data structure and performing the splice operation on the candidate edge and a new quad edge.